11116 - Babel towers/11116.by.Jan.cpp

   1 /*
   2    Author       :   Jan
   3    Problem Name :   Babel Towers
   4    Algorithm    :   Math, Center of Masses
   5    Complexity   :   O(n^2)
   6 */
   7
   8 #include <vector>
   9 #include <list>
  10 #include <map>
  11 #include <set>
  12 #include <queue>
  13 #include <stack>
  14 #include <algorithm>
  15 #include <iostream>
  16 #include <cstdio>
  17 #include <cmath>
  18 #include <cstdlib>
  19 #include <cctype>
  20 #include <string>
  21
  22 using namespace std;
  23
  24 #define min(a,b) ((a) < (b) ? (a) : (b))
  25 #define max(a,b) ((a) > (b) ? (a) : (b))
  26
  27 #define CLR(a) memset(a,0,sizeof(a))
  28
  29 #define MAX 1001
  30 const double eps = 1e-7;
  31
  32 int n;
  33 double sumMass[MAX],sumX[MAX],sumY[MAX];
  34
  35 struct circle
  36 {
  37    double x,y,r;
  38 }C[MAX];
  39
  40 bool input()
  41 {
  42    scanf("%d",&n);
  43    if(!n) return false;
  44    for(int i=1;i<=n;i++)
  45    {
  46       scanf("%lf %lf %lf",&C[i].x,&C[i].y,&C[i].r);
  47       sumX[i]=sumX[i-1]+C[i].x*C[i].r*C[i].r;
  48       sumY[i]=sumY[i-1]+C[i].y*C[i].r*C[i].r;
  49       sumMass[i]=sumMass[i-1]+C[i].r*C[i].r;
  50    }
  51    return true;
  52 }
  53
  54 void process()
  55 {
  56    int i,j;
  57    double sX,sY,sM,X,Y;
  58
  59    for(i=1;i<=n;i++)
  60    {
  61       for(j=i-1;j>=1;j--)
  62       {
  63          sM=sumMass[i]-sumMass[j];
  64          sX=sumX[i]-sumX[j];
  65          sY=sumY[i]-sumY[j];
  66          X=sX/sM;
  67          Y=sY/sM;
  68          if((X-C[j].x)*(X-C[j].x)+(Y-C[j].y)*(Y-C[j].y)+eps>C[j].r*C[j].r)
  69             break;
  70       }
  71       if(j) break;
  72    }
  73    if(i==n+1) puts("Feasible");
  74    else printf("Unfeasible %d\n",i-1);
  75 }
  76
  77 int main()
  78 {
  79    while(input())
  80    {
  81       process();
  82    }
  83    return 0;
  84 }